#include <stdio.h>
#include <stdlib.h>
#define SHADOWS 3

/*Esta funcion fue extraida de:
	http://en.wikipedia.org/wiki/Lagrange_interpolation */
float lagrangeInterpolatingPolynomial(float pos[], float val[], int degree,
	float desiredPos);

int main(void)
{
	int p, i;
	float * pos, * val;
	int lagrange = 0, shamir = 0, day = 0, month = 0;

	char * months[] = {"February", "January", "March", "April", "May",
		"June", "July", "August", "September", "October", "November", "December"};

	printf("This program uses Lagrange Interpolation to obtain the Shamir Secret using 3 shadows\n");
	printf("Enter the value of p:\n");
	scanf("%d", &p);
	printf("Now enter the value of the shadows with the format \"x,y\" like \"1,123\"\n");
	if((pos = calloc(SHADOWS, sizeof(float))) == NULL)
	{
		fprintf(stderr, "Memory allocation error");
		return 1;
	}

	if((val = calloc(SHADOWS, sizeof(float))) == NULL)
	{
		fprintf(stderr, "Memory allocation error");
		return 1;
	}
	for(i = 0; i < SHADOWS; i++)
	{
		printf("Enter shadow number %d:\n", i);
		scanf("%f,%f", &(pos[i]), &(val[i]));
	}
	lagrange = (int)lagrangeInterpolatingPolynomial(pos, val, SHADOWS, 0);
	shamir = lagrange % p;
	printf("\n\nThe value of the Shamir secret is: %d\n\n", shamir);
	day = shamir / 100;
	month = shamir % 100 - 1;
	if(month <= 12 && month > 0 && day > 0 && day <= 31)
		printf("==The date is %s %d==\n\n", months[month], day);
	else
		printf("==The Shamir secret is an invalid date==\n\n");

}

float lagrangeInterpolatingPolynomial(float pos[], float val[], int degree,
	float desiredPos)
{
   float retVal = 0;
 	int i, j;
   for (i = 0; i < degree; ++i) {
      float weight = 1;

      for (j = 0; j < degree; ++j) {

         if (j != i) {
            weight *= (desiredPos - pos[j]) / (pos[i] - pos[j]);
         }
      }

      retVal += weight * val[i];
   }

   return retVal;
}


